import java.util.Stack;

/*
 * @author zzr
 * @date: 2025/10/18  11:20
 * @description: 找到两个指定节点的最近公共祖先
 * 如果二叉树保存了父亲节点的地址，这个题目就可以转换成求链表的相交节点
 * 获取 root 到 node 路径上的所有节点：使用深度优先搜索 + 回溯
 * 1. 遇到节点，先将其压入栈内
 * 2. 若该节点是目标节点，说明找到路径，返回 true
 * 3. 若该节点不是目标节点，则递归搜索左子树和右子树
 * 4. 若左右子树都没有找到目标节点，则说明该节点不在路径上
 * 将其从栈中弹出，进行回溯
 * 5. 返回false
 */
public class Demo29 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
        if (root == null || node == null) {
            return false;
        }
        stack.push(root);
        if (root == node) {
            // 检查当前节点是否为目标节点
            return true;
        }

        // 遍历左子树
        boolean flgLeft = getPath(root.left, node, stack);
        if (flgLeft) return true;
        // 遍历右子树
        boolean flgRight = getPath(root.right, node, stack);
        if (flgRight) return true;

        // 如果左右子树都没有直接返回 true
        // 则说明当前节点并不是路径的一部分，需要从栈中弹出（回溯）
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;

        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        getPath(root, p, stackP);
        getPath(root, q, stackQ);

        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        if (sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            while (size != 0) {
                stackP.pop();
                size--;
            }
        } else {
            int size = sizeQ - sizeP;
            while (size != 0) {
                stackQ.pop();
                size--;
            }
        }
        while (!stackP.isEmpty() && !stackQ.isEmpty()) {
            if (stackP.peek() == stackQ.peek()) {
                return stackP.peek();
            }
            stackP.pop();
            stackQ.pop();
        }
        return null;
    }

}
